#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

capacity = 18       # 双肩包空间容量

weights = [7, 8, 6]
values  = [9, 15, 7]



def max_bag_value(capacity, last_idx):
    # 返回: 背包容量capacity,  选择装入[0, last_idx]商品 的最优价值
    # last_idx == 2: 表示可选商品为[0, 1, 2]
    # last_idx == 1: 表示可选商品为[0, 1]
    # last_idx == 0: 表示可选商品为[0]

    # 如果没有商品可选
    if last_idx == - 1:
        return 0

    # 如果背包容量为0
    if capacity == 0:
        return 0

    if weights[last_idx] > capacity:
        # last_idx 太重了, 无法选择, 等同于不存在
        max_value = max_bag_value(capacity, last_idx-1)

    else:
        # 选择商品last_idx 的情况
        method1_select_val = max_bag_value(capacity - weights[last_idx-1], last_idx-1) + values[last_idx]

        # 不选择商品last_idx 的情况
        method2_drop_val = max_bag_value(capacity, last_idx-1)

        max_value = max(method1_select_val, method2_drop_val)

    return max_value


def test():
    num_of_product = len(values)
    max_value = max_bag_value(capacity, num_of_product-1)
    print("value", max_value)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
